class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        //构建前缀和矩阵
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        
        //使用前缀和数组
        vector<vector<int>> ret(m, vector<int>(n));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                // + 1解决mat数组与dp数组的映射关系问题
                int x1 = max(0,i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1,j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +dp[x1 - 1][y1 - 1];
            }

        return ret;
    }
};

//利用将lowbit置0的特点，来统计1的个数·
class Solution {
public:
    // int hammingWeight(uint32_t n) 
    // {
    //     int cnt = 0;
    //     while(n)
    //     {
    //         n &= (n-1);
    //         cnt++;
    //     }
    //     return cnt;
    // }
    
    //暴力遍历
    int hammingWeight(uint32_t n) 
    {
        int cnt = 0;
        for(int i = 0; i < 32; i++)
        {
            if(n & (1 << i))
                cnt++;
        }
        return cnt;
    }
};

class Solution {
public:

    int countlowbit(int n)
    {
        int cnt = 0;
        while(n)
        {
            n &= n - 1;
            cnt++;
        }
        return cnt;
    }
    
    vector<int> countBits(int n)
    {
        vector<int> ret(n+1);
        int cnt = 0;
        for(int i = 0;i <= n; i++)
        {
            ret[i] = countlowbit(i);
        }
        return ret;
    }
};

//动态规划-最高有效位
class Solution {
public:
    vector<int> countBits(int n) 
    {
        vector<int> ret(n+1);
        int highbit = 0;
        for(int i = 1; i <= n; i++)
        {
            if((i & (i - 1))== 0)//2的整数次幂就置为highbit
                highbit = i;
            ret[i] = ret[i - highbit] + 1;
        }
        return ret;
    }
};
